package main

import (
	"fmt"
)

// 实现两个有序序列的归并
// t 临时slice
func merge(nums, t []int, low, mid, high int) {
	// 1. 拷贝进去 临时 slice
	//for i, num := range nums[low: high + 1] {  // 不能这样复制，下表从 0开始！！
	//	t[i] = num
	//}
	for i := low; i <= high; i++ {
		t[i] = nums[i]
	}
	// 2. 比较归并
	i, k := low, low
	j := mid + 1
	for i <= mid && j <= high {
		if t[i] < t[j] {
			nums[k] = t[i]
			i++
		} else {
			nums[k] = t[j]
			j++
		}
		k++
	}
	// 3. 处理剩余
	for i <= mid {
		nums[k] = t[i]
		i++
		k++
	}
	for j <= high {
		nums[k] = t[j]
		j++
		k++
	}
}

func MergeSort(nums, t []int, low, high int) {
	if low < high {
		mid := low + (high-low)/2
		MergeSort(nums, t, low, mid)
		MergeSort(nums, t, mid+1, high)
		merge(nums, t, low, mid, high)
	}
}

// 还有链表版的归并排序
// 参考力扣（148. 排序链表）题解： https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution/
// 这里实现的是 普通的归并排序，递归形式（自顶向下归并排序）
// 还有一种 O(1) 空间复杂度的（自底向上归并排序）写法。

type ListNode struct {
	Val  int
	Next *ListNode
}

func mergeList(h1, h2 *ListNode) *ListNode {
	// 伪节点
	dumpyHead := &ListNode{}
	t := dumpyHead
	for h1 != nil && h2 != nil {
		if h1.Val <= h2.Val {
			t.Next = h1
			h1 = h1.Next
		} else {
			t.Next = h2
			h2 = h2.Next
		}
		t = t.Next
	}
	if h1 != nil {
		t.Next = h1
	} else if h2 != nil {
		t.Next = h2
	}
	return dumpyHead.Next
}

func MergeSortLinked(h *ListNode) *ListNode {
	if h.Next == nil {
		return h
	}
	// 快慢指针进行分层
	slow, fast := h, h
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	// 找到两个链表头
	left, right := h, slow.Next
	// 断开
	slow.Next = nil
	// 递归
	l1 := MergeSortLinked(left)
	l2 := MergeSortLinked(right)
	return mergeList(l1, l2)
}

func main() {
	arr := []int{54, 26, 93, 17, 77, 31, 44, 55, 20}
	t := make([]int, len(arr))
	MergeSort(arr, t, 0, len(arr)-1)
	fmt.Println(arr)

	a := 's'
	b := "12345"
	var c = b[1]
	fmt.Println(a, b, c)
	fmt.Println('a', 'z')
}
